package com.zjj.algorithm.learning.leetcode.matrix;

/**
 * 221. 最大正方形 中档题
 * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 * <p>
 * 输入：matrix = [
 * ["1","0","1","0","0"],
 * ["1","0","1","1","1"],
 * ["1","1","1","1","1"],
 * ["1","0","0","1","0"]
 * ]
 * 输出：4
 * <p>
 * 输入：matrix = [["0","1"],["1","0"]]
 * 输出：1
 * 示例 3：
 * <p>
 * 输入：matrix = [["0"]]
 * 输出：0
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 300
 * matrix[i][j] 为 '0' 或 '1'
 *
 * @author zjj_admin
 * @date 2022/12/20 15:42
 */
public class MaximalSquare {

    public static void main(String[] args) {
        char[][] matrix = new char[][]{
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '0', '1', '1', '1'},
                {'1', '0', '1', '1', '1'}};

        int res = maximalSquare2(matrix);
        System.out.println("res = " + res);
    }


    /**
     * 动态规划算法
     * <p>
     * 时间
     * 6 ms
     * 击败
     * 90.39%
     * 内存
     * 53.3 MB
     * 击败
     * 51.3%
     *
     * @param matrix
     * @return
     */
    public static int maximalSquare2(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }

    /**
     * 超出时间限制
     *
     * @param matrix
     * @return
     */
    public static int maximalSquare(char[][] matrix) {
        int h = matrix.length;
        int w = matrix[0].length;
        int res = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (matrix[i][j] == '1') {
                    int max = maxSquare(i, j, matrix);
                    res = Math.max(res, max);
                }
            }
        }
        return res;
    }

    /**
     * 获取以 （i，j）为坐标向右下方延展的最大的正方形
     *
     * @param i      第几行
     * @param j      第几列
     * @param matrix 矩阵
     * @return
     */
    private static int maxSquare(int i, int j, char[][] matrix) {
        int res = 1;
        //总行数
        int h = matrix.length;
        //总列数
        int w = matrix[0].length;
        int _len = 1;
        while (true) {
            if (isValid(i + _len, j + _len, h, w)) {
                //判断矩形中是不是全为 '1'
                boolean flag = true;
                for (int m = i; m < i + _len; m++) {
                    for (int n = j; n < j + _len; n++) {
                        if (matrix[m][n] != '1') {
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag) {
                    res = _len * _len;
                } else {
                    break;
                }
            } else {
                break;
            }
            _len++;
        }
        return res;
    }

    private static boolean isValid(int i, int j, int h, int w) {
        return i >= 0 && i <= h && j >= 0 && j <= w;
    }
}
